πŸ“‚ μ—°κ²° 리슀트 (Linked List)

@Seongukbaek Posted May 18, 2022 Β· Updated May 18, 2022 Β· 2 min read

🧷 μ—°κ²° 리슀트 (Linked List)

연속적인 λ©”λͺ¨λ¦¬ μœ„μΉ˜μ— μ €μž₯λ˜μ§€ μ•ŠλŠ” μ„ ν˜• 데이터 ꡬ쑰둜, 포인터λ₯Ό μ‚¬μš©ν•΄ μ—°κ²°λœλ‹€. 각 λ…Έλ“œλŠ” 데이터 ν•„λ“œμ™€ λ‹€μŒ λ…Έλ“œμ— λŒ€ν•œ μ°Έμ‘°λ₯Ό ν¬ν•¨ν•˜λŠ” λ…Έλ“œλ‘œ κ΅¬μ„±λœλ‹€.

πŸͺš μ™œ μ‚¬μš©ν•˜λ‚˜?

배열은 λΉ„μŠ·ν•œ μœ ν˜•μ˜ μ„ ν˜• 데이터λ₯Ό μ €μž₯ν•˜λŠ”λ° μ‚¬μš©ν•  수 μžˆμ§€λ§Œ μ œν•œ 사항이 μžˆλ‹€.

  • λ°°μ—΄μ˜ ν¬κΈ°λŠ” 고정적이기에 미리 μ €μž₯될 μš”μ†Œμ˜ μˆ˜μ— λŒ€ν•œ 정보가 ν•„μš”ν•˜λ‹€.
  • μƒˆλ‘œμš΄ μš”μ†Œλ₯Ό μ‚½μž…ν•˜λŠ” 것은 λΉ„μš©μ΄ 많이 λ°œμƒν•œλ‹€. (곡간을 ν• λ‹Ήν•˜κ³ , κΈ°μ‘΄ μš”μ†Œλ₯Ό μ „λΆ€ 이동)

πŸͺš μž₯점

  • 크기가 동적이닀.
  • μ‚½μž…, μ‚­μ œκ°€ μš©μ΄ν•˜λ‹€.

πŸͺš 단점

  • μž„μ˜λ‘œ μ•‘μ„ΈμŠ€λ₯Ό ν—ˆμš©ν•  수 μ—†λ‹€, 즉 첫 번째 λ…Έλ“œλΆ€ν„° 순차적으둜 μš”μ†Œμ— μ ‘κ·Όν•΄μ•Ό ν•œλ‹€. (이진 탐색 λΆˆκ°€λŠ₯)
  • ν¬μΈν„°μ˜ μ—¬λΆ„μ˜ λ©”λ‘œλ¦¬ 곡간이 λͺ©λ‘μ˜ 각 μš”μ†Œλ§ˆλ‹€ ν•„μš”ν•˜λ‹€.

πŸͺš Single Linked List

import java.util.*; class Node { int data; Node next; Node(int data) { this.data = data; next = null; } } class LinkedList { Node head; public void printList() { Node n = head; while (n != null) { System.out.println(n.data + " "); n = n.next; } } // λ…Έλ“œ μΆ”κ°€ public void push(Node n) { Node h = head; if (head == null) { head = n; return; } while (h.next != null) { h = h.next; } h.next = n; } // νŠΉμ • λ…Έλ“œ 뒀에 λ…Έλ“œ μΆ”κ°€ public void push(Node n, int insertAt) { Node h = head; if (head == null) { head = n; return; } while (h.data != insertAt) { h = h.next; } Node tmp = null; h.next = tmp; h.next = n; n.next = tmp; } } class Main { public static void main(String[] args) { LinkedList ll = new LinkedList(); for (int i = 1; i < 4; i++) { ll.push(new Node(i)); } ll.printList(); } }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€